package com.atues.hash.firstMissingPositive41;

/**
 * @description:
 * @author: liang
 * @time: 2025-03-02 16:07
 */
class Solution {
    public int firstMissingPositive(int[] nums) {
        //原地哈希，因为nums数组中最小的正数为1，最大的正数为n+1（数组为值为1，。。。。n）
        //所以只要使得nums[nums[i] - 1] = nums[i]，舍得数组中填放正确的值及填方nums[i] = i+1,其中 i为0，n-1
        int t1;
        for(int i = 0 ; i < nums.length ; i ++){
            //判断下标是否符合数组长度，然后再判读是否已经放入了合适的位置

            if(nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]){
                int tmp = nums[nums[i] - 1];//被更换的位置的值，不需要管这个值在数组哪个位置（及他的数组下标）只需要知道他是否该放入哈希表，以及放入的位置，放入的位置和他的值有关；
                nums[nums[i] - 1] = nums[i];
                while(tmp>=1 && tmp <= nums.length && nums[tmp - 1] != tmp){//判断是否可以更换位置
                    t1 =  nums[tmp - 1];
                    nums[tmp - 1] = tmp;
                    tmp = t1;
                }
            }
        }
        int i ;
        for(i = 0 ; i < nums.length ; i++){
            if(nums[i] != i + 1)
                return i + 1;
        }
        return  i+1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,2,0};
        int i = solution.firstMissingPositive(nums);
        System.out.println(i);
    }
}
